{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../common/rfsoc_book_banner.jpg\" alt=\"University of Strathclyde\" align=\"left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Notebook Set I\n",
    "\n",
    "---\n",
    "\n",
    "## 01 - OFDM Fundamentals\n",
    "\n",
    "The notebook introduces the fundamental theory of Orthogonal Frequency Division Multiplexing (OFDM). OFDM is a form of digital Multi-Carrier Modulation (MCM) that has been adopted as the basis of several modern wireless standards such as Wi-Fi, 4G and now 5G.   \n",
    "\n",
    "* Provide an overview of the OFDM transmission process\n",
    "* Discuss the role of the Inverse Fast Fourier Transform (IFFT) & Fast Fourier Transform (FFT) in OFDM  \n",
    "* Provide a brief summary of multipath channels\n",
    "* Demonstrate the purpose of the Cyclic Prefix (CP)\n",
    "\n",
    "##  Table of Contents \n",
    "\n",
    "* [1. Introduction](#introduction)\n",
    "* [2. OFDM Transmitter](#ofdmtx)\n",
    "   * [2.1. Baseband Symbol Generation](#baseband)\n",
    "   * [2.2. Serial to Parallel Converter](#s2p)\n",
    "   * [2.3. Sub-carrier Modulation](#scmod)\n",
    "   * [2.4. Sub-carrier addition](#scadd)\n",
    "   * [2.5. Modulation using the IFFT](#IFFT)\n",
    "* [3. The Multipath Channel](#multipath)\n",
    "   * [3.1. Effect of Multipath Channel on OFDM Signals](#mpofdm)\n",
    "* [4. The Cyclic Prefix](#cp)\n",
    "  * [4.1. One Tap Equaliser](#onetap)\n",
    "* [5. Updated OFDM Transmitter](#tx_update)\n",
    "* [6. Conclusion](#conclusion)\n",
    "\n",
    "## Revision\n",
    "* **v1.0** | 05/12/22 | *First Revision*\n",
    "\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Introduction <a class=\"anchor\" id=\"introduction\"></a>\n",
    "\n",
    "In this notebook, the fundamentals of OFDM are introduced. OFDM is a digital MCM method used in several wireless communications standards, such as the IEEE 802.11 family (Wi-Fi), 4G Long Term Evolution (LTE) and most recently 5G New Radio (NR). \n",
    "\n",
    "In OFDM, a high rate symbol stream (QPSK, QAM etc.) is transmitted as a sum of several parallel low rate streams, that each modulate a different orthogonal sub-carrier. OFDM allows for a computationally efficient channel equalisation process and provides the ability to completely eliminate Inter Symbol Interference (ISI). Also, the use of orthogonal sub-carriers produces a very spectrally efficient transmission.  \n",
    "\n",
    "The orthogonal modulation and demodulation processes are equivalent to the Inverse Discrete Fourier Transform (IDFT) and Discrete Fourier Transform (DFT) respectively, allowing OFDM to be implemented efficiently using FFT algorithms. The use of independent sub-carriers also leads to a convenient multiple access scheme, where the available sub-carriers are shared among several different users. This is known as Orthogonal Frequency Division Multiple Access (OFDMA). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. OFDM Transmitter <a class=\"anchor\" id=\"ofdmtx\"></a>\n",
    "\n",
    "In this section, we will go through each step of the OFDM modulation process. A high level overview of an OFDM transmitter is shown below:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"images/ofdm_tx_1 copy.svg\" style=\"width: 900px;\"/> \n",
    "    <figcaption><b>Figure 1: OFDM transmitter architecture.</b></figcaption>\n",
    "</figure>     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Firstly, we have to import the necessary libraries and helper functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import necessary libraries \n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import math\n",
    "from scipy import signal\n",
    "\n",
    "# Import helper function\n",
    "from rfsoc_book.helper_functions import symbol_gen, psd, frequency_plot, scatterplot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To begin with, let us define the modulation scheme (BPSK, QPSK or 16-QAM) and symbol rate of the initial high rate symbol stream:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mod_scheme = '16-QAM' # Modulation scheme \n",
    "fs = 20e6 # Initial symbol rate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In OFDM systems, the baseband modulation scheme is a form of Quadrature Amplitude Modulation (QAM). It can vary from BPSK at the lowest to 1024-QAM or higher in the latest standards. Using higher levels of QAM allows a larger amount of data to be transmitted within a fixed bandwidth. The rate of the initial symbol stream is denoted by,$f_{s}$, since it is equivalent to the sampling rate in OFDM systems. Let's now define the number of sub-carriers, $N$: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 64 # No. of sub-carriers "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As indicated by the diagram, the high rate data stream is divided into $N$ parallel low rate streams using a serial to parallel converter. As a result, the symbol rate, $R$, of each parallel stream is:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "R = fs/N # symbol rate of parallel data streams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and the symbol period $T$ is: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "T = 1/R # symbol period of parallel data streams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each lower rate stream modulates a different one of the $N$ sub-carriers. The value $N$ is chosen to ensure that the channel frequency repsonse is effectively constant across the sub-carrier bandwidth (equivalent to $R$). This facilitates simplified frequency domain equalisation of each sub-carrier in the receiver. \n",
    "\n",
    "The process of equalising several parallel sub-carriers in the frequency domain is much more computationally efficient than the time domain equalisation traditionally used in single carrier systems. The efficient equalisation scheme allows OFDM to be deployed over large bandwidths and thus to support very high data rate applications. \n",
    "\n",
    "Having independent sub-carriers also leads to OFDMA, which is an efficient multiple access scheme where groups of sub-carriers are assigned to different users. OFDMA is employed in 4G LTE, 5G NR and some of the later Wi-Fi standards.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The sub-carrier spacing (in frequency) is also set equal to $R$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "deltaf = R # Sub-carrier spacing "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is because orthognality can only be acheieved using frequencies that have an integer number of periods in $T$, i.e $1/T$ and its integer multiples. Hence, the spacing between sub-carriers is $\\Delta f = 1/T = R$.  \n",
    "\n",
    "Orthogonality is useful because it allows tight overlap of sub-carriers in frequency, mitigating the need for guard bands to keep the sub-carriers separated. This leads to a much more efficient use of bandwidth than can be achieved with generic MCM. Moreover, it removes the need for expensive bandpass filters to recover the sub-carriers in the receiver. \n",
    "\n",
    "Also, notice the number of sub-carriers has been set to a power of 2. This is because later we'll show that OFDM is implemented using FFT algorithms, which use power of 2 lengths.\n",
    "\n",
    "As indicated in Figure 1, the different lower rate streams modulating each sub-carrier  are summed together to produce the OFDM signal. Since the symbol period on each sub-carrier is $T$, it follows that the OFDM symbol period is also $T$ and the OFDM symbol rate is $f_{s}/N$. Note, as will be described in [Section 4](#cp), the addition of a CP reduces the symbol rate and hence the achievable throughput of the OFDM system. However, the CP is very important for maintaining sub-carrier orthogonality and combatting ISI due to multipath propagation effects.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1. Baseband Symbol Generation <a class=\"anchor\" id=\"baseband\"></a>\n",
    "\n",
    "With reference to Figure 1, we will now go through each step in generating an OFDM signal. The first step is generating the data symbols, e.g. BPSK, QPSK and 16-QAM etc. at baseband, i.e. before up-conversion to Radio Frequency (RF). In pratice, we begin with data bits and map these to symbols, but we will skip this stage here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_ofdm = 500 # No. of OFDM symbols\n",
    "nsym = n_ofdm * N # No. of data symbols \n",
    "\n",
    "# Generate data symbols\n",
    "data_serial = symbol_gen(nsym,mod_scheme)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice we have set the number of OFDM symbols, $N_{ofdm}$, that we want to generate. Since each OFDM symbol is comprised of a sum of $N$ parallel data symbols each modulating a different sub-carrier, it follows that we need to generate $NN_{ofdm}$ data symbols. The baseband constellation is plotted below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot constellation \n",
    "scatterplot(data_serial.real,data_serial.imag,ax=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2. Serial to Parallel Converter <a class=\"anchor\" id=\"s2p\"></a>\n",
    "\n",
    "We can now convert the high rate stream to $N$ parallel low rate streams: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Matrix to hold parallel low rate data streams\n",
    "data_parallel = np.zeros((N,n_ofdm),np.complex64)  \n",
    "j= 0\n",
    "\n",
    "# Serial to Parallel converter\n",
    "for i in range(n_ofdm):\n",
    "    data_parallel[:,i] = data_serial[j:j+N]\n",
    "    j = j + N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3. Sub-carrier Modulation <a class=\"anchor\" id=\"scmod\"></a>\n",
    "\n",
    "The parallel low rate streams then modulate each of the sub-carriers. In this example, all sub-carriers are being used to transmit data symbols. However, in real systems, pilot sub-carriers are embedded in the OFDM symbol for synchronisation and channel estimation tasks in the receiver. Also, the outer sub-carriers, i.e. those closest to the edges of the transmit frequency band, are often left blank to mitigate the need for expensive anti-imaging and anti-aliasing filters in the transmitter and receiver respectively. These are known as null sub-carriers. \n",
    "\n",
    "The construction of a single OFDM symbol can be expressed mathematically as: \n",
    "\n",
    "$$x[n]=\\sum_{k=0}^{N-1} X[k]e^{j2 \\pi k (\\Delta f / f_{s}) n},$$\n",
    "\n",
    "where $x[n]$ is the OFDM symbol, $X[k]$ is the $k^{th}$ input symbol, $\\Delta f$ is the sub-carrier spacing, $\\textit{n}$ is the sample index and $\\textit{k}$ is the sub-carrier index. Recall that the OFDM symbol period is $T$, which equals $N/f_{s}$. Therefore, there are $N$ samples per OFDM symbol. \n",
    "\n",
    "At this stage, we'll generate the $N$ orthogonal sub-carriers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sc = np.zeros((N,N),np.complex64) # Matrix to hold sub-carriers \n",
    "k = np.arange(N) # Define sub-carrier indices i.e. [0,1....N-1]\n",
    "n = k # Discrete time index  \n",
    "\n",
    "# Generate sub-carriers  \n",
    "for i in range(N):\n",
    "    sc[i,:] = np.exp(1j*2*math.pi*k[i]*(deltaf/fs)*n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you might expect, there are $N$ sub-carriers and $N$ samples per sub-carrier. Note we are only generating $N$ samples of each sub-carrier here, since they are indentical for all subsequent periods of $N$. Let's now modulate the sub-carriers with the parallel data streams:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Modulate sub-carriers with data symbols   \n",
    "sc_mod = np.zeros((N,n_ofdm*N),np.complex64)\n",
    "j = 0\n",
    "\n",
    "for i in range(n_ofdm):\n",
    "    sc_mod[:,j:j+N] = sc * data_parallel[:,i][:, np.newaxis]\n",
    "    j = j + N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Having modulated the sub-carriers, we will now stop and inspect the frequency spectra of the different sub-carriers. This will be useful in understanding the choice of sub-carrier spacing made earlier in the notebook. Before that though, we need to review some theory in order to understand what to expect. \n",
    "\n",
    "As you'll have noticed, no explicit pulse shaping is performed on each of the parallel data streams (e.g. Root Raised Cosine). Therefore, the pulse shaping is implicitly rectangular, with a duration $T$.    \n",
    "\n",
    "From fundamental signal processing theory, we know that a rectangular pulse of duration $T$ has a sinc frequency spectrum, whose zero crossings occur at $\\pm{1/T}$ $\\textit{Hz}$, $\\pm{2/T}$ $\\textit{Hz}$,$\\pm{3/T}$ $\\textit{Hz}$ and so on... Therefore, if we choose a minumum sub-carrier spacing of $1/T$ $\\textit{Hz}$, the centre frequency or maximum effect point of each sub-carrier will correspond to the zero crossings of all other sub-carriers. As a result, the sub-carriers are orthogonal. The sub-carrier spacing is given by:\n",
    "\n",
    "$$ \\Delta f = \\frac{1}{T}. $$\n",
    "\n",
    "Substituting the previous equation for $\\textit{T}$ gives:\n",
    "\n",
    "$$ \\Delta f = \\frac{1}{N / f_{s}} = \\frac{f_{s}}{N}. $$\n",
    "\n",
    "Therefore, this is why we chose a sub-carrier spacing of $\\Delta f = f_{s}/N$ earlier in the notebook. It is the smallest spacing that guarantees orthogonality between the sub-carriers. \n",
    "\n",
    "In the following code cell, we extract two sub-carriers and plot their Power Specral Densities (PSDs):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract two sub-carriers and plot together \n",
    "sc_1 = sc_mod[0,:] \n",
    "sc_2 = sc_mod[2,:]\n",
    "\n",
    "# Estimate PSDs of sub-carriers \n",
    "fft_s = 512\n",
    "wtype = 'Rectangle' \n",
    "overlap = 0\n",
    "psd_est_1 = psd(sc_1,fft_s,wtype,overlap)\n",
    "psd_est_2 = psd(sc_2,fft_s,wtype,overlap)\n",
    "\n",
    "# Convert to dB\n",
    "epsilon = 1e-9; # Add to avoid divide by zero errors\n",
    "psd_db_1 = 10 * np.log10(psd_est_1+epsilon) \n",
    "psd_db_2 = 10 * np.log10(psd_est_2+epsilon)\n",
    "\n",
    "# Frequency axis \n",
    "freqs = np.linspace(-fs/2,(fs/2 - (fs/fft_s)), fft_s) \n",
    "\n",
    "# Plot PSDs\n",
    "fig=plt.figure(figsize=(5,4), dpi=100)\n",
    "frequency_plot(freqs, np.fft.fftshift(psd_db_1), ax=None)\n",
    "frequency_plot(freqs, np.fft.fftshift(psd_db_2), ax=None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, it can be observed that the sub-carriers have a sinc frequency spectrum. Also, due to the choice of spacing, the centre of each sub-carrier correpsonds to the zero crossing of the other sub-carrier. \n",
    "\n",
    "It can also be observed that there is interference between the sub-carriers at other frequencies. However, in the receiver, we sample the sub-carrier at its maximum effect point, where the interference from the other sub-carriers is zero.. \n",
    "\n",
    "To summarise, the orthogonality property enables the data to be recovered perfectly despite the fact that the sub-carriers are interfering with one another (just not at the maximum effect points). This mitigates the need for guard bands to keep the sub-carriers separated and expensive bandpass filters to recover each sub-carrier at the receiver. This makes OFDM a very efficient form of MCM.  \n",
    "\n",
    "In practice, channel and hardware induced impairments will cause the sub-carrier maximum effect points to drift from the ideal frequencies, leading to Inter Carrier Interference (ICI). This manifests as a form of additive noise, so we aim to minimise ICI as much as possible. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4. Sub-carrier Addition <a class=\"anchor\" id=\"scadd\"></a>\n",
    "\n",
    "Finally, the sub-carriers are summed to create the OFDM symbol: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ofdm_data = np.sum(sc_mod,0,np.complex64)/N"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5. Modulation using the IFFT <a class=\"anchor\" id=\"IFFT\"></a>\n",
    "\n",
    "In practice, the orthogonal modulation process shown above requires $\\textit{N}$ complex oscillators at both transmitter and receiver. This makes this form of MCM prohibitively costly as $\\textit{N}$ gets larger. However, this cost can be reduced significantly if we realise that the modulation and demodulation processes are equivalent to an IDFT and DFT respectively. As such, we can implement OFDM using FFT algorithms, which are much more computationally efficient. \n",
    "\n",
    "As it turns out, it is quite easy to prove that the OFDM modulation process is equivalent to an IDFT. Recall, that the sub-carrier spacing for OFDM, $\\Delta_{f}$, is given by: \n",
    "\n",
    "$$\\Delta_{f} = \\frac{f_{s}}{N}.$$\n",
    "\n",
    "Therefore, if we substitute this equation into our subcarrier modulation equation, it reduces to:\n",
    "\n",
    "$$x[n]=\\sum_{k=0}^{N-1} X[k]e^{j2 \\pi k n / N},$$\n",
    "\n",
    "which is the equation for the IDFT minus the $1/N$ scaling factor. \n",
    "\n",
    "We can now compare the OFDM symbols generated using the orthogonal modulation process with the symbols generated by the IFFT to show that they are equivalent:  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define function to modulate using IFFT \n",
    "def ifft_mod(symbols,N):\n",
    "    ofdm_data = np.fft.ifft(symbols,N)\n",
    "    return ofdm_data\n",
    "\n",
    "#  Generate OFDM symbols using IFFT modulation   \n",
    "ofdm_data_ifft = np.zeros(n_ofdm*N,np.complex64)\n",
    "j = 0\n",
    "\n",
    "for i in range(n_ofdm):    \n",
    "    ofdm_data_ifft[j:j+N] = ifft_mod(data_serial[j:j+N],N)\n",
    "    j = j + N  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compare OFDM symbols generated using orthogonal modulation and IFFT respectively\n",
    "plt.plot(ofdm_data[0:(2*N)].real,'b')\n",
    "plt.plot(ofdm_data_ifft[0:(2*N)].real,'--r')\n",
    "plt.title('Orthogonal Modulation vs. IFFT (I)')\n",
    "plt.xlabel('n (sample index)')\n",
    "plt.ylabel('Amplitude')\n",
    "plt.legend(('Orthogonal Modulation','IFFT'))\n",
    "\n",
    "plt.figure(2)\n",
    "\n",
    "plt.plot(ofdm_data[0:(2*N)].imag,'b')\n",
    "plt.plot(ofdm_data_ifft[0:(2*N)].imag,'--r')\n",
    "plt.title('Orthogonal Modulation vs. IFFT(Q)')\n",
    "plt.xlabel('n (sample index)')\n",
    "plt.ylabel('Amplitude')\n",
    "plt.legend(('Orthogonal Modulation','IFFT'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The plots show that the data produced using orthogonal modulation is equivalent to the IFFT. We can also confirm this by measuring the Mean Square Error (MSE) between the data streams:   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mse = np.mean(abs(ofdm_data-ofdm_data_ifft)**2)\n",
    "mse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. The Multipath Channel <a class=\"anchor\" id=\"multipath\"></a>\n",
    "\n",
    "In a typical wireless channel, the transmitted signal is reflected off objects (buildings, vehicles, foliage etc) in the signal path, leading to several delayed and attenuated copies of the signal arriving at the receiver. The constructive and destructive interference of the multipath components lead to fading of the received signal. The fading effect is frequency selective, i.e. different frequencies experience different amounts of fading. \n",
    "\n",
    "The channel is characterised by its delay spread, $d_{s}$, which is the difference in time between the first and last multipath arrivals. In the frequency domain, the channel is characterised by its coherence bandwidth, $B_{c}$, which is the range of frequencies over which the fading effect is approximately constant. The two quantities are approximately inversely proportional: \n",
    "\n",
    "$$d_{s} \\approx \\frac{1}{B_{c}}.$$\n",
    "\n",
    "Depending on the characteristics of the transmitted signal, the channel can be classified as a flat fading or frequency selective fading channel. \n",
    "\n",
    "The channel is flat fading when the symbol period is long compared to the channel delay spread, \n",
    "\n",
    "$$ T_{sym} \\gg d_{s}, $$\n",
    "\n",
    "where $T_{sym}$ represents the symbol period. In the frequency domain, the signal bandwidth is small compared to the coherence bandwidth, \n",
    "\n",
    "$$ B \\ll B_{c},$$\n",
    "\n",
    "where $B$ is the signal bandwidth. A flat fading channel is relatively simple to equalise or compenstate for and there is limited ISI.\n",
    "\n",
    "Conversely, the channel is experienced as frequency selective if the symbol period is small compared to delay spread, \n",
    "\n",
    "$$ T_{sym} \\ll d_{s}, $$\n",
    "\n",
    "and the signal bandwidth is large compared to the coherence bandwidth, \n",
    "\n",
    "$$ B \\gg B_{c}. $$\n",
    "\n",
    "The ISI is more severe in a frequency selective channel and it is more challenging to equalise. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1. Effect of Multipath channels on OFDM signals <a class=\"anchor\" id=\"mpofdm\"></a>\n",
    "\n",
    "In OFDM, we choose the number of sub-carriers such that their bandwidths are much smaller than $B_{c}$ or equivalently that $T$ is much greater than $d_{s}$. As such, each sub-carrier experiences a flat fading channel. This leads us towards the \"one tap\" equaliser, which reduces the equalisation process to a single complex scaling per sub-carrier. The one tap equaliser is a major advantage of OFDM. In addition, the use of orthogonal sub-carriers increases the spectral efficiency of the transmission. \n",
    "\n",
    "However, in practice, the multipath channel violates sub-carrier orthogonality and introduces ISI, meaning these advantages are lost. \n",
    "\n",
    "A multipath channel can be modelled as a Finite Impulse Response (FIR) filter, since the output signal is equivalent to the convolution of the input signal with the channel impulse response. Each filter coefficient represents a single resolvable multipath component and the length of the filter is dictated by $d_{s}$ i.e. the time difference between the first and last multipath arrivals. \n",
    "\n",
    "Let us consider a simple three tap channel filter, as illustrated below:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"images/filter copy.svg\" style=\"width: 500px;\"/> \n",
    "    <figcaption><b>Figure 2: Multipath channel filter design.</b></figcaption>\n",
    "</figure>     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note this is not an accurate representation of a real channel, but is sufficient for understanding the effects of multipath on OFDM signals. In proper baseband channel models, we use complex weights drawn from a normal distribution. There are also different amounts of delay between the different weights (paths).    \n",
    "\n",
    "Recall that the OFDM symbol is simply composed of a sum of amplitude and phase modulated complex sinusoids or sub-carriers (formed using IFFT). In order to illustrate the effects of multipath on OFDM, we will consider only a single sub-carrier. The effects described will apply equally to all other sub-carriers. Let us concentrate on the sub-carrier at $k = 1$ as below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sub-carrier at k = 1 or fs/N Hz\n",
    "n = np.arange(64)\n",
    "k = 1\n",
    "sc = np.exp(1j*2*math.pi*k*n/N) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's extract the real or in-phase component of the sub-carrier and plot it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract In-Phase component\n",
    "sc_real = sc.real\n",
    "\n",
    "fig=plt.figure(figsize=(5,4), dpi=100)\n",
    "plt.plot(sc_real,'b')\n",
    "plt.title('In-Phase Component of k=1 sub-carrier')\n",
    "plt.xlabel('n (sample index)')\n",
    "plt.ylabel('Amplitude')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As can be observed, the sub-carrier is a perfect cosinusoid and has one full period within $T$ seconds or $N$ samples i.e. the OFDM symbol period. As we know, this sub-carrier would be amplitude and / or phase modulated depending on the underlying modulation scheme, e.g. QPSK, 16-QAM. However, we will leave it unmodulated at the present time. \n",
    "\n",
    "Before passing the signal through the channel filter, it is first necessary to review some theory in order to understand what the output signal will look like. Note, we are modelling the channel using a standard digital FIR filter in this example. However, the effects will be similar for a real life channel.\n",
    "\n",
    "When a finite time signal with duration $N$ samples is passed through an $L$ tap FIR filter, the output signal comprises three distinct stages: the \"transient\", the \"steady-state\" and the \"decay\" stages. These are illustrated in Figure 3, along with the duration of each stage:  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"images/output_signal copy.svg\" style=\"width: 700px;\"/> \n",
    "    <figcaption><b>Figure 3: Stages of the output signal.</b></figcaption>\n",
    "</figure>     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As can be deduced by looking at Figure 2, the filter memory consists of the current sample and $L-1$ past samples. \n",
    "\n",
    "The transient stage occurs when the $L-1$ past samples still include sample periods before the signal existed e.g. $x[-1]$, $x[-2]$ etc. assuming the signal begins at $x[0]$. As such, the transient stage is $L-1$ samples long.\n",
    "\n",
    "The steady-state stage starts as soon as the filter memory is fully occupied with signal samples. The steady-state portion of the output signal is $N-L+1$ samples long. \n",
    "\n",
    "The decay stage occurs when the filter memory is occupied by both signal samples and future samples (which again do not exist). This also lasts for $L-1$ samples.\n",
    "\n",
    "Adding up the durations of each each stage, we find that the output signal has a total duration of $N+L-1$ samples. It is worth noting that for an infinite input signal, the output signal would always be in steady-state, i.e. there would be no transient or decay stages. However, in the real world we are only interested in finite time signals.\n",
    "\n",
    "In the real multipath channel, the length of the transient and decay stages equals $d_{s}$ i.e. the difference in time between the first and last multipath arrivals. The steady-state period would equal $T$ - $d_{s}$. \n",
    "\n",
    "We will now pass the sub-carrier through the multipath channel filter: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Multipath channel  \n",
    "h = np.array([0.9,0.3,0.05])\n",
    "sc_filt = np.convolve(sc_real, h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From what we described, the output signal should have a length of $N+L-1$ = $64+3-1=66$ samples. This can be confirmed as follows: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(sc_filt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now plot the filtered sub-carrier: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fig=plt.figure(figsize=(5,4), dpi=100)\n",
    "plt.plot(sc_filt,'r')\n",
    "xvals = np.arange(66)\n",
    "xvals = xvals[2:64]\n",
    "plt.plot(xvals,sc_filt[2:64],'b')\n",
    "\n",
    "plt.title('Filtered sub-carrier')\n",
    "plt.xlabel('n (sample index)')\n",
    "plt.ylabel('Amplitude')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above plot, the transient and decay stages are plotted in red. Conversely, the steady-state stage is plotted in blue. \n",
    "\n",
    "It can be observed that the sub-carrier period of $N$ samples includes the transient and the steady-state periods. This can be confirmed by adding the transient and steady-state durations i.e. $L-1$ + $N-L+1$ = $N$. \n",
    "\n",
    "This is problematic because it means that the sub-carrier is no longer sinusoidal across $N$ samples or $T$ seconds. The transient destroys the sinuosoidal shape of the sub-carrier within the $N$ sample window. This also occurs for all other sub-carriers in the OFDM symbol. This leads to a violation of the sub-carrier orthogonality. It is also necessary for the amplitude and phase of each sub-carrier to remain constant over a duration of $T$ seconds or $N$ samples to maintain orthogonality. However, this is no longer the case - it's actually constant during the steady-state period i.e. $N-L+1 = 64-3+1 = 62$ samples. \n",
    "\n",
    "The decay stage is also an issue because it causes interference with the same sub-carrier in the subsequent OFDM symbol. This is due to the fact that the second symbol is sent immediately after the first symbol and so on i.e there is no guard interval between symbols (yet). This phenomenon is known as ISI and causes a severe performance degradation.\n",
    "\n",
    "Clearly, this discussion has demonstrated that multipath channels have a detrimental effect on OFDM signals. This would appear to mitigate any potential advantages of using OFDM. However, these issues can be resolved by the addition of a special guard interval called the Cyclic Prefix (CP). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. The Cyclic Prefix <a class=\"anchor\" id=\"cp\"></a>\n",
    "\n",
    "The CP is formed by extracting a portion of the end of the OFDM symbol and appending it to the front. The CP is made to be longer than the expected delay spread. This is possible because the OFDM symbol period is much greater than the delay spread.  \n",
    "\n",
    "In order to demonstrate the addition of a CP, we will again consider the in-phase component of a single sub-carrier.\n",
    "\n",
    "Refrerring to Figure 2, we can see that the first multipath component arrives immediately and the last multipath component arrives 2 samples later, meaning that $d_{s}$ equals 2 sample periods. We will therefore choose a CP length of 4 (slightly longer than strictly necessary). In the following code cell, we will append the CP samples and plot the resulting waveform:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract CP samples \n",
    "cp = sc_real[60:64]\n",
    "\n",
    "# Append to front of sub-carrier \n",
    "sc_cp = np.concatenate((cp, sc_real))\n",
    "\n",
    "# Plot resulting waveform \n",
    "fig=plt.figure(figsize=(5,4), dpi=100)\n",
    "plt.plot(sc_cp,'r')\n",
    "xvals = np.arange(68)\n",
    "xvals = xvals[4:68]\n",
    "plt.plot(xvals,sc_cp[4:68],'b')\n",
    "\n",
    "plt.title('Sub-carrier with CP')\n",
    "plt.xlabel('n (sample index)')\n",
    "plt.ylabel('Amplitude')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above plot, the CP samples are highlighted in red. The first thing we notice is that there is no discontinuity between the CP and the sub-carrier. This is due to the fact that there is exactly one period of the sub-carrier in the OFDM symbol period i.e. $N$ = 64 samples in this example. There is also no discontinuity for the other sub-carriers because they all have an integer number of periods within the OFDM symbol period. This is beneficial since it prevents generation of spurious high frequency components, due to discontinuities between the symbol and the guard interval. However, ultimately, there are still discontinuities between the OFDM symbols themselves. These discontinuities are addressed using windowing techniques.   \n",
    "\n",
    "The full OFDM symbol (including CP) can be formed by adding CPs to each individual sub-carrier and summing the resulting waveforms together. This is equivalent to first using the IFFT to generate the sum of modulated orthogonal sub-carriers (OFDM symbol) and then adding a CP at the beginning of the symbol. As we've learned, the latter approach is used in practice. \n",
    "\n",
    "Having described the mechanics of adding the CP, we can now demonstrate how it addresses the problems caused by the multipath channel. In order to do this, we will pass the sub-carrier with CP through the channel and plot the output signal: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Pass sub-carrier with CP through channel filter \n",
    "sc_filt_cp = np.convolve(sc_cp, h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the cyclic extension of 4 samples, the input signal is now $N+4 = 68$ samples long. Using Figure 3, we can calculate that the output signal will have a length of $N+L-1 = 68+3-1 = 70$ samples. This is confirmed below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(sc_filt_cp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now plot the received waveform:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Plot received waveform \n",
    "fig=plt.figure(figsize=(5,4), dpi=100)\n",
    "plt.plot(sc_filt_cp,'r')\n",
    "xvals = np.arange(70)\n",
    "xvals = xvals[4:68]\n",
    "plt.plot(xvals,sc_filt_cp[4:68],'b')\n",
    "\n",
    "plt.title('Filtered sub-carrier with CP')\n",
    "plt.xlabel('n (sample index)')\n",
    "plt.ylabel('Amplitude')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above plot, the CP samples and the decay transient are plotted in red. Again, the steady-state portion is plotted in blue.\n",
    "\n",
    "Let's focus on the CP samples. Recall that the transient of the multipath channel is 2 samples long and that the CP is 4 samples long. This means that the CP is \"on\" or being transmitted during the transient of the multipath channel and therefore is able to absorb it. Note the CP is slightly longer than necessary to absorb the transient.\n",
    "\n",
    "Now, let's look at the steady-state portion of the signal. Immediately, we can now that it is $N$ samples long and that it has the desired sinusoidal shape. Therefore, the CP preserves the sinusoidal shape of the sub-carriers and thus their orthogonality is maintained. Furthermore, the amplitude and phase of each sub-carrier is constant over the window of $N$ samples or $T$ seconds, as required. \n",
    "\n",
    "Finally, we still have the decay transient. Although it is not shown explicitly, the decay transient occurs during the CP of the next symbol. Therefore, the CP of the next symbol absorbs ISI from the current symbol. As long as the CP is longer than $d_{s}$, the CP will completely eliminate ISI. In general, the CP will absorb a combination of the transient stage of the current symbol and the decay stage of the previous symbol. \n",
    "\n",
    "To summarise, a block of $N$ symbols (QPSK, 16-QAM etc.) are passed into an $N$ point IFFT and then $N_{cp}$ samples are extracted from the end of the OFDM symbol and appended to the front to form the CP. Therefore, the final symbol length after CP addition is $N_{ofdm} = N_{u} + N_{cp}$, where $N_{u}$ is called the \"useful symbol\", i.e. the part of the OFDM symbol that carries data and pilot signals (in practical implementations). \n",
    "\n",
    "It should be noted that although the CP is important for combatting ISI, it does involve adding redundancy to the OFDM signal which therefore reduces the spectral efficiency and hence achievable throughput. The addition of a CP essentially involves lengthening the symbol in time and hence reducing the symbol rate and throughput by a factor of $N/(N+N_{cp}).$ Therefore, the CP must not be any longer than is absolutely necessary, in order to minimse its impact on the achievable throughput.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1. One Tap Equaliser <a class=\"anchor\" id=\"onetap\"></a>\n",
    "\n",
    "In addition to addressing issues related to multipath channels, the CP has one other important role to play in OFDM systems. Namely, it leads to the so-called one tap equaliser. \n",
    "\n",
    "In order to understand this, we need to recall the convolution theorem. The convolution theorem states that linear convolution in time is equivalent to multiplication in frequency, followed by the inverse transformation. However, this is only true for continuous time signals.  \n",
    "\n",
    "In discrete time, the convolution theorem is slightly different. In this case, multiplication in frequency followed by inverse transformation is equivalent to periodic or circular convolution in the time domain. What is circular convolution?\n",
    "\n",
    "To take a familiar example, circular convolution arises if we pass a discrete-time signal with period $N$ through a standard FIR filter. From now on, a signal with period $N$ will be defined as $N$ periodic. Assuming an $N$ periodic input signal, $x[n]$, and filter weights, $h[m]$, the output signal, $y[n]$, is given by:\n",
    "\n",
    "$$ y[n] = \\sum_{m=0}^{L-1} h[m] x_{N}[n-m], $$ \n",
    "\n",
    "where $L$ is again the number of coefficients, $m$ is the coefficient index and $x_{N}$ denotes that $x[n]$ is $N$ periodic. Since $x[n]$ is $N$ periodic, it follows that $y[n]$ is also $N$ periodic, and hence the convolution is circular.    \n",
    "\n",
    "So why is multiplication in discrete frequency equivalent to circular convolution in discrete time? We can answer this by considering how we might perform convolution using $H[k]$ and $X[k]$ i.e. the $N$ point DFTs of $h[m]$ and $x[n]$ respectively. This would be achieved by taking the $N$ point IDFT of the product of $H[k]$ and $X[k]$,    \n",
    "\n",
    "$$ IDFT\\{H[k] X[k]\\}.$$\n",
    "\n",
    "It is possible to perform a full mathematical derivation and show that the above operation produces a single period of $y[n]$ i.e. the circular convolution of $h[m]$ and $x[n]$. However, we can see this somewhat intuitively by recalling that the time domain sequence produced by an IDFT is always $N$ periodic, where $N$ is the IDFT size. This is because the complex exponential basis functions are $N$ periodic."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, why is this relevant to OFDM? Well, we would like to exploit the fact that convolution in time is equivalent to multiplication in frequency for equalisation after the FFT in the receiver. If the OFDM system is designed correctly, then the channel response is reduced to a single complex multiplication per sub-carrier after the FFT. The channel can then be equalised via a complex division per sub-carrier or one tap equaliser.\n",
    "\n",
    "However, the problem remains that the channel will perform a linear convolution. So how can we make the convolution circular so that the above relation is true? Examining the equation for circular convolution, we can see that a way to do this is to periodically extend the input signal. Obviously, we can't extend it infinitely so the question is how much extension is actually necessary? \n",
    "\n",
    "The question can be reformulated more precisely by asking how much we need to periodically extend $x[n]$ to produce one period of $y[n]$. Note, we only need to compute one period of $y[n]$, since it is periodic. Recall that an FIR filter has a memory consisting of the current sample and $L-1$ past samples. This means we only have to consider at most $L-1$ samples before the beginning of $x[n].$ Therefore, it is only necessary to periodically extend $x[n]$ by a minimum of $L-1$ samples to the left, since anything beyond that is irrelevant to the calculation.    \n",
    "\n",
    "For a real world channel, it's neccesary to periodically extend the signal by at least $d_{s}$ seconds to the left. The number of samples required depends on the sampling rate. As we know, the OFDM system is designed such that $T$ or $N$ is a much longer period of time than $d_{s}$. Therefore, each OFDM symbol only has to be periodically extended by a fraction of a period to the left. As you'll recognise, this is exactly what we have done with the CP. \n",
    "\n",
    "To confirm that this works, let's revist our filtered sub-carrier with CP from before and just extract the steady-state portion of the waveform i.e. discard the CP and decay samples at the beginning and end respectively:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Extract steady-state portion of output signal\n",
    "sc_ss = sc_filt_cp[4:68]  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The steady-state waveform should correspond to one period of the circular convolution of the filter (channel) impulse response and the sub-carrier. We can prove this by first calculating the circular convolution using the FFT method:   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate H[k] and X[k]\n",
    "Hk = np.fft.fft(h,N)\n",
    "Xk = np.fft.fft(sc_real,N)\n",
    "\n",
    "# IDFT of  H[k] x X[k] \n",
    "y = np.fft.ifft(Hk * Xk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now measure the MSE between the two signals to confirm that the steady-state waveform is equivalent to the circular convolution of the sub-carrier and the impulse response:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mse = np.mean(abs(y-sc_ss)**2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Therefore, by adding a CP with an appropriate length to each OFDM symbol, we obtain one repetition of the circular convolution of each OFDM symbol and the channel impulse response. Subsequently, after the FFT is performed in the receiver, the underlying data symbols in each OFDM symbol can be equalised as:\n",
    "\n",
    "$$ \\hat{X}[k] = \\frac{Y[k]}{\\hat{H}[k]}, $$\n",
    "\n",
    "where $\\hat{X}[k]$ are the estimated data symbols, $Y[k]$ are the received symbols and $\\hat{H}[k]$ is the estimated channel frequency response. This calculation is performed for each individual sub-carrier $k$. This one-tap equaliser is very computationally efficient and is one of the main advantages of OFDM.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Updated OFDM Transmitter <a class=\"anchor\" id=\"tx_update\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the learning of the previous sections, we can draw an updated diagram of an OFDM transmitter:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"images/ofdm_tx_2 copy.svg\" style=\"width: 1000px;\"/> \n",
    "    <figcaption><b>Figure 4: Updated OFDM transmitter design.</b></figcaption>\n",
    "</figure>   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first stage in the process is mapping the data bits to symbols i.e. BPSK, QPSK, 16-QAM etc. The symbols are then organised into groups of $N$ (in practice, less than this due to the use of pilots and null sub-carriers) and a series of $N$ point IFFTs are performed to generate the OFDM symbols. Finally, a CP is added to the beginning of each symbol to maintain orthogonality and prevent ISI and facilitate the one-tap equaliser. Although not indicated in Figure 4, the data bits are normally scrambled and then Forward Error Correction (FEC) and interleaving are performed before the symbol mapping. After the CP is added, the signal is up converted to Radio Frequency (RF) and transmitted across the channel."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. Conclusion <a class=\"anchor\" id=\"conclusion\"></a>\n",
    "\n",
    "In conclusion, this notebook has introduced the fundamental theory of OFDM. Due to a number of advantages, OFDM has been chosen as the basis of several well known communications standards such as the IEEE 802.11 family (Wi-Fi), 4G LTE and most recently 5G NR. \n",
    "\n",
    "In this notebook, we provided an overview of the OFDM transmission processs and showed that modulation and demodulation can be  performed efficiently using an IFFT/FFT pair. We then briefly reviewed multipath channels and showed that they cause a loss of sub-carrier orthogonality and ISI. Subsequently, it was shown that these problems can be resolved by adding a special guard interval between symbols known as the CP. The CP is formed by copying a fraction of the end of the symbol and appending it to the front. The use of a CP prevents any discontinuity between the guard interval and the OFDM symbol. Finally, we showed that the addition of a CP produces a circular convolution with the channel and leads to the computationally efficient one tap equaliser. \n",
    "\n",
    "In the next notebook, we will demonstrate an OFDM transceiver including equalisation in the receiver. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "[⬅️ Previous Notebook](../notebook_H/05_fec_bit_error_analysis.ipynb) || [Next Notebook 🚀](02_ofdm_python_transceiver.ipynb)\n",
    "\n",
    "Copyright © 2023 Strathclyde Academic Media\n",
    "\n",
    "---\n",
    "---"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
